!***************************************************
! This subroutine implements linear interpolation
!***************************************************
!z: interpolated value
!n: grid points
!a: belief value at which the relevant function value is computed
!y: value function array (value function evaluated at each grid point)
!x: prior grid
!flag: indicating whether 'a' falls into a grid

    
SUBROUTINE sub_interp1(x,y,a,n,z)

USE mod_types
USE mod_parameters

IMPLICIT NONE

INTEGER:: n,flag,i
REAL(dp),DIMENSION(n)::x,y
REAL(dp)::a,z,t



IF (a<=x(n) .and.a>=x(1) ) THEN

flag=0
i=n

DO WHILE (flag<1)

    i=i-1
    IF (a>=x(i)) THEN
    flag=i
    END IF
           
END DO

END IF

IF (a>x(n)) THEN
flag=n-1

END IF

IF (a<x(1)) THEN
flag=1

END IF

t=(a-x(flag))/(x(flag+1)-x(flag))

z=(1-t)*y(flag)+t*y(flag+1)

END  
